package _linklist;

import org.junit.Assert;
import org.junit.Test;

import java.util.HashSet;
import java.util.Set;

/*
142. 环形链表 II
给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

https://leetcode.cn/problems/linked-list-cycle-ii/description/
https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html

 * 输入：head = [3,2,0,-4], pos = 1
 * 输出：返回索引为 1 的链表节点
 *
 *
 * 输入：head = [1,2], pos = 0
 * 输出：返回索引为 0 的链表节点
 *
 * 输入：head = [1], pos = -1
 * 输出：返回 null
 */
public class leetcode_142 {
    @Test
    public void test_1() {
        ListNode l1 = new ListNode(3);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(0);
        ListNode l4 = new ListNode(-4);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l2;

        ListNode actual = detectCycle(l1);
        ListNode expected = l2;
        Assert.assertEquals(expected, actual);
    }

    @Test
    public void test_2() {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        l1.next = l2;
        l2.next = l1;

        ListNode actual = detectCycle(l1);
        ListNode expected = l1;
        Assert.assertEquals(expected, actual);
    }

    @Test
    public void test_3() {
        ListNode l1 = new ListNode(1);

        ListNode actual = detectCycle(l1);
        ListNode expected = null;
        Assert.assertEquals(expected, actual);
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    private ListNode detectCycle(ListNode head) {
//        return detectCycle1(head);
        return detectCycle2(head);
    }

    private ListNode detectCycle1(ListNode head) {
        // 方法1 ： 哈希表 :
        // T - N
        // S - N
        Set<ListNode> set = new HashSet<>();
        ListNode p = head;
        while (p != null) {
            if (set.contains(p)) {
                return p;
            } else {
                set.add(p);
            }
            p = p.next;
        }
        return p;
    }

    private ListNode detectCycle2(ListNode head) {
        // 快慢指针法
        // T - N
        // S - 1
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {
                ListNode t1 = fast;
                ListNode t2 = head;
                while (t1 != t2) {
                    t1 = t1.next;
                    t2 = t2.next;
                }
                return t1;
            }
        }
        return null;
    }
}
